package com.ly.algorithm.offerpointer;
import	java.util.ArrayList;

import java.util.LinkedList;
import java.util.List;

/**
 * @Classname Offer34
 * @Description
 *
 * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 *
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 * 返回:
 *
 * [
 *    [5,4,11,2],
 *    [5,8,4,5]
 * ]
 *
 *
 * @Date 2021/1/29 16:02
 * @Author 冷心影翼
 */
public class Offer34 {

    public static void main(String[] args) {
        Solution34 solution34 = new Solution34();
        List<List<Integer>> lists = solution34.pathSum(TreeNode.init(new int[]{2,-1,3}), 5);
        lists.forEach(System.out::println);
    }

}


class Solution34 {

    private List<List<Integer>> res;

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new ArrayList<> ();
        if(root == null) {
            return res;
        }
        dfs(root,0,sum,new LinkedList<>());
        return res;
    }

    public void dfs(TreeNode root,int total,int sum,List<Integer> path) {

        if(root == null) {
            return;
        }
        path.add(root.val);
        total += root.val;
        if(total == sum && root.left == null && root.right == null) {
            res.add(new ArrayList<>(path));
        }
        dfs(root.left,total,sum,path);
        dfs(root.right,total,sum,path);
        path.remove(path.size()-1);

    }
}
